package leetcode.code1423;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//超出内存限制  28 / 40 个通过测试用例
public class Solution3 implements IDebug {

	long R = (long) 1e5;
	long RR = R * R;

	public int maxScore(int[] cardPoints, int k) {
		int len = cardPoints.length;
		Map<Long, Integer> dp = new HashMap<>();
		return this.find(cardPoints, 0, len - 1, k, dp);
	}

	private int find(int[] cardPoints, int left, int right, int k, Map<Long, Integer> dp) {
		if (k == 1 || (k > 0 && left == right)) {
			int max = Math.max(cardPoints[left], cardPoints[right]);
			return max;
		}
		Long key = left + right * R + k * RR;
		if (dp.containsKey(key)) {
			return dp.get(key);
		}
		int max = cardPoints[left] + this.find(cardPoints, left + 1, right, k - 1, dp);
		max = Math.max(max, cardPoints[right] + this.find(cardPoints, left, right - 1, k - 1, dp));
		dp.put(key, max);
		return max;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(202, this.maxScore(HelpDebug.str2array3("[1,79,80,1,1,1,200,1]"), 3));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
